class DoublyLinkedList:
    class _Node:
        def __init__(self, data, prev, next):
            self._data = data
            self._prev = prev
            self._next = next

    def __init__(self):
        self._head = None
        self._tail = None
        self._size = 0
    
    def __repr__(self):
        node = self._head
        nodes = []
        while node is not None:
            nodes.append(node._data)
            node = node._next
        nodes.append("None")
        return " <-> ".join(nodes)
    
    def __len__(self):
        return self._size
    
    def is_empty(self):
        return self._size == 0

    def get_head(self):
        return self._head._data if self._head is not None else 'Empty'
    
    def get_tail(self):
        return self._tail._data if self._tail is not None else 'Empty'

    def add_tail(self, e):
        """
        Add an element to the back of the tail
        """
        newest = self._Node(e, self._tail, None)
        if self.is_empty():
            self._head = newest
        else:
            self._tail._next = newest
        self._tail = newest
        self._size += 1

    def pop_tail(self):
        """
        Remove and return the last element
        """
        if self.is_empty():
            raise Empty("It's Empty")
        answer = self._tail
        if self._size == 1:
            self._head = None
            self._tail = None
        else:
            self._tail = self._tail._prev
            self._tail._next = None
        self._size -= 1
        return answer._data
    
    def pop_head(self):
        """
        Remove and return the first element
        """
        if self.is_empty():
            raise Empty("It's Empty")
        answer = self._head
        self._head = self._head._next
        if self._head is not None:
            self._head._prev = None
        else:
            self._tail = None
        self._size -= 1
        return answer._data
    
    def add_head(self, e):
        """
        Add an element to the front of the head
        """
        newest = self._Node(e, None, self._head)
        if self.is_empty():
            self._tail = newest
        else:
            self._head._prev = newest
        self._head = newest
        self._size += 1
    
    def search(self, e):
        """
        Search for an element in the linked list
        """
        current = self._head
        while current is not None:
            if current._data == e:
                return True
            current = current._next
        return False
    
    def reverse_repr(self):
        """
        Return a string representation traversing from tail to head
        """
        node = self._tail
        nodes = []
        while node is not None:
            nodes.append(node._data)
            node = node._prev
        nodes.append("None")
        return " <-> ".join(nodes)


class Empty(Exception):
    def __init__(self, *args):
        super().__init__(*args)


if __name__ == '__main__':
    dll = DoublyLinkedList()

    dll.add_tail('pomme')
    dll.add_tail('banana')
    dll.add_tail('orange')
    dll.add_tail('kiwi')
    print(f"Size: {dll._size}")
    print(f"Forward: {dll}")
    print(f"Backward: {dll.reverse_repr()}")
    print(f"Head: {dll._head._data}")
    print(f"Tail: {dll._tail._data}")
    
    print(f"\nPopping head: {dll.pop_head()}")
    print(f"After pop_head: {dll}")
    
    print(f"\nPopping tail: {dll.pop_tail()}")
    print(f"After pop_tail: {dll}")
    
    print(f"\nSearch 'banana': {dll.search('banana')}")
    print(f"Search 'pomme': {dll.search('pomme')}")
    
    dll.add_head('fraise')
    print(f"\nAfter add_head('fraise'): {dll}")
